import java.util.ArrayList;
import java.util.List;

/**
 * 212. 单词搜索 II
 * https://leetcode-cn.com/problems/word-search-ii/
 */
public class Solutions_212 {
    public static void main(String[] args) {
        char[][] board = {{'o', 'a', 'a', 'n'},
                          {'e', 't', 'a', 'e'},
                          {'i', 'h', 'k', 'r'},
                          {'i', 'f', 'l', 'v'}};
        String[] words = {"oath", "pea", "eat", "rain"};  // output: {'eat', 'oath'}

//        char[][] board = {{'a', 'b'},
//                          {'c', 'd'}};
//        String[] words = {"abcb"};  // output: {}

//        char[][] board = {{'a', 'a'}};
//        String[] words = {"a"};  // output: {"a"}

        List<String> result = findWords(board, words);
        System.out.println(result);
    }

    // 上、下、左、右四个方向
    private static int[][] direct = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static int row = 0;
    private static int col = 0;
    private static List<String> res = null;

    private static TrieNode root = null;
    /**
     * 解法二：前缀树 + 回溯（1ms）
     */
    public static List<String> findWords(char[][] board, String[] words) {
        res = new ArrayList<>();
        root = new TrieNode();
        row = board.length;
        col = board[0].length;

        // 构造前缀树
        addWordsToTrie(words);
        // 递归查找
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 判断所遍历矩阵的字符，是否在 root 的了节点中存在
                if (root.containsKey(board[i][j])) {
                    backtrack2(board, i, j, root);
                }
            }
        }
        return res;
    }

    public static void backtrack2(char[][] board, int i, int j, TrieNode node) {
        char c = board[i][j];
        // 获取到子节点
        TrieNode cur = node.get(c);
        if (cur == null) {
            return;
        }
        if (cur.getWord() != null) {
            res.add(cur.getWord());
            // 找到后即清空，保证不会添加重复的字符串到结果集中
            cur.setWord(null);
            return;
        }
        // 标记状态
        board[i][j] = '#';
        // 向 [i, j] 的上、下、左、右，四个方向上，判断字符是否在字典树中存在
        for (int[] dir : direct) {
            int m = i + dir[0];
            int n = j + dir[1];
            if (m < 0 || m >= row || n < 0 || n >= col || board[m][n] == '#') {
                // 超出矩阵范围，或者已经访问过
                continue;
            }
            backtrack2(board, m, n, cur);
        }
        // 还原状态
        board[i][j] = c;
        if (cur.getCount() == 0) {
            // 加上此段代码，会到 1ms
            node.put(c, null);
            node.setCount(node.getCount() - 1);
        }
    }

    /**
     * 对 words 字符串数组，构造树
     */
    public static void addWordsToTrie(String[] words) {
        for (String word : words) {
            TrieNode curNode = root;
            char[] arr = word.toCharArray();
            for (char c : arr) {
                if (!curNode.containsKey(c)) {
                    curNode.put(c, new TrieNode());
                    // 记录下 curNode 节点下的非空节点个数
                    curNode.setCount(curNode.getCount() + 1);
                }
                curNode = curNode.get(c);
            }
            curNode.setWord(word);
        }
    }

    /**
     * 解法一：暴力回溯（1ms）
     */
    public static List<String> findWords2(char[][] board, String[] words) {
        row = board.length;
        col = board[0].length;
        res = new ArrayList<>();
        // 对每一个字符串，都进行递归匹配
        for (String word : words) {
            char[] arr = word.toCharArray();
            loop:
                // 遍历二维数组
                for (int i = 0; i < row; i++) {
                    for (int j = 0; j < col; j++) {
                        if (board[i][j] == arr[0]) {
                            // 首字符匹配，进入递归
                            if (backtrack(board, arr, 0, i, j)) {
                                res.add(word);
                                break loop;
                            }
                        }
                    }
                }
        }
        return res;
    }

    public static boolean backtrack(char[][] board, char[] arr, int index, int i, int j) {
        if (index == arr.length - 1) {
            // 结束条件：该条递归路径上找到全部 arr 字符
            return arr[index] == board[i][j];
        }
        if (arr[index] != board[i][j]) {
            // 结束条件：路径上的字符不匹配
            return false;
        }
        // 当前字符标记一个状态，通过异或 32，将小写字母变成大写
        board[i][j] ^= 32;
        // 以 [i, j] 为原点，向上、下、左、右，四个方向上递归
        for (int[] dir : direct) {
            int m = i + dir[0];
            int n = j + dir[1];
            if (m < 0 || m >= row || n < 0 || n >= col) {
                // 范围越界
                continue;
            }
            // 递归
            boolean res = backtrack(board, arr, index + 1, m, n);
            if (res) {
                // 递归完成，还原状态
                board[i][j] ^= 32;
                return true;
            }
        }
        // 递归完成，还原状态
        board[i][j] ^= 32;
        return false;
    }
}
